package ch4tree;

import java.util.HashMap;

public class Ex6 {

	static TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null) {
			return null;
		}
		
		TreeNode left = root.left;
		if (left != null && covers(left, p) && covers(left, q)) {
			return commonAncestor(left, p, q);
		}
		
		TreeNode right = root.right;
		if (right != null && covers(right, p) && covers(right, q)) {
			return commonAncestor(right, p, q);
		}
		
		return root;
	}

	private static boolean covers(TreeNode root, TreeNode p) {
		if (root == p) {
			return true;
		}
		
		TreeNode left = root.left;
		if (left != null && covers(left, p)) {
			return true;
		}
		
		TreeNode right = root.right;
		if (right != null && covers(right, p)) {
			return true;
		}
		
		return false;
	}
	
	public static void main(String... argv) {
//	        4               
//	       / \       
//	      /   \      
//	     /     \     
//	    /       \    
//	    2       6       
//	   / \     / \   
//	  /   \   /   \  
//	  1   3   5   7   
//	               \ 
//	               8 
	    int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };
	    HashMap<Integer,TreeNode> bst = Chapter.createMinimalBST(array, true);
//		Chapter.rotateLeft(bst.get(6));
		TreeNode node = bst.get(4);
		BTreePrinter.printNode(node);
		
		for (int i=0; i<array.length-1; i++) {			
			for (int j=i+1; j<array.length; j++) {
				TreeNode ancestor = commonAncestor(node, bst.get(i+1), bst.get(j+1));
				System.out.println("i="+(i+1)+" j="+(j+1)+" commonAncestor="+ancestor);
			}
		}
		int a = 1;
	}
}
